<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        //时间复杂度：O(n^2) 空间复杂度:O(1) 
        //稳定性：插入排序稳定的排序算法，满足条件arr[target] < arr[j]才发生交换，这个条件可以保证值相等的元素的相对位置不变。
        function insertionSort(arr) {
            //从数组的第二位开始往左比较，所以i=1
            for (let i = 1; i < arr.length; i++) {
                let target = i; //这个是右边没排序的第一个数，第一次循环默认位第二个数
                for (let j = i - 1; j >= 0; j--) {//遍历前面排好的
                    //将target与左边排序好的数比较，如果比较小，则与被比较的数交换位置
                    if (arr[target] < arr[j]) {
                        [arr[target], arr[j]] = [arr[j], arr[target]];
                        //交换完之后target往前插入一位
                        target = j;
                    } else {
                        //如果前面没有比target小的数，退出循环
                        break;
                    }
                }
            }
            return arr;
        }
        const arr = [1, 8, 5, 2, 13, 7, 42, 64, 2];
        console.log(insertionSort(arr));

    </script>
</body>

</html>